package org.example.sword2offer.primary;

import javax.swing.*;

/**
 * @author: lynn
 * @Descript: 重建二叉树，注意树的节点定义,由前序，中序构建二叉树
 * Question 5  https://www.cnblogs.com/dddyyy/p/10682890.html
 * @date: 2021/3/7 23:16
 * @version: 1.0
 */

/**
 * 前序遍历：首先要从根节点往下，然后在往上，再访问二叉树的根节点，在访问左右子树节点,
 * 特点:第一个数就是根结点而后是左子树的先序序列和右子树的先序序列
 * 中序遍历：先反问左节点，然后是根节点，之后是右节点。 中序遍历的结果是二叉树排序后的结构，就是肉眼看过去，长啥样的，
 * 就是一一对应下来排序后的结果。
 * 后序遍历:先反问左子树，在访问右子树，然后访问该节点。一个典型的应用是在内存的释放，先释放完孩子节点，在释放这个节点本身。
 * 层序遍历（广度优先遍历）：以节点为第一层，逐步向下一层遍历，借助队列这种先进先出的数据结构。
 * 广度优先遍历相对于深度优先遍历的优先在于： 有的时候可以更快的找到你想要查询的元素，主要是用于搜索策略上
 */

/**
 *
 *  前序遍历：根结点 ---> 左子树 ---> 右子树
 *  中序遍历：左子树---> 根结点 ---> 右子树
 *  后序遍历：左子树 ---> 右子树 ---> 根结点
 *  二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。思路：根据前序遍历找到根，根据中序遍历找到左右子树，依次递归。归结：根 > 左 > 右
 *
 */


public class Q5_ReConstructBTByPreAndMid_H {
    public static void main(String[] args) {

        int[] pre={1,2,4,7,3,5,6,8};
        int[] mid={4,2,7,1,5,3,8,6};
        Q5_ReConstructBTByPreAndMid_H test=new Q5_ReConstructBTByPreAndMid_H();
        TreeNode treeNode=test.construct(pre,mid);
    }

    // https://www.bilibili.com/video/BV1LJ411y7Xa?from=search&seid=8365346870055617476 b站讲解
    private  TreeNode<Integer> construct(int[] pre,int[] mid){
        //pre是代表前序, mid是代表中序
        return help(pre,mid,0,pre.length-1,0,mid.length-1);
    }

    public  TreeNode help(int[] pre,int [] mid,int preLeft,int preRight,int midLeft,int midRight){
        if (preLeft>=pre.length || midLeft>=mid.length || preLeft>preRight || midLeft>midRight) //fixme
            return null;
        int value=pre[preLeft]; //fixme
        TreeNode node=new TreeNode(value);
        int count=midLeft;  //找到root的位置，并计算相应的长度
        while (mid[count]!=value){
            count++;
        }
        count-=midLeft;
        //通过前序和中序标定左子树和右子树的范围
        node.leftNode=help(pre,mid,preLeft+1,preLeft+count,midLeft,midLeft+count-1);//fixme
        node.rightNode=help(pre,mid,preLeft+count+1,preRight,midLeft+count+1,midRight); //fixme
        return node;
    }



    private static class TreeNode<T>{
        T data; //树中的值
        TreeNode leftNode; //左子树
        TreeNode rightNode; // 右子树
        //初始化定义节点
        TreeNode(T data){
            this.data=data;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public TreeNode getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;
        }

        public TreeNode getRightNode() {
            return rightNode;
        }

        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }

        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            // root
            generateString(null, 0, res);
            return res.toString();
        }

        // 生成以node为根节点，深度为depth的描述二叉树的字符串
        private void generateString(TreeNode node, int depth, StringBuilder res){

            if(node == null){
                res.append(generateDepthString(depth) + "null\n");
                return;
            }

            res.append(generateDepthString(depth) + node.data + "\n");
            generateString(node.leftNode, depth + 1, res);
            generateString(node.rightNode, depth + 1, res);
        }

        private String generateDepthString(int depth){
            StringBuilder res = new StringBuilder();
            for(int i = 0 ; i < depth ; i ++)
                res.append("--");
            return res.toString();
        }
    }

    // 前序遍历以node为根的二分搜索树, 递归算法
    private void preOrder(TreeNode node){
        if(node == null) return;
        System.out.println(node.data);//访问改节点
        preOrder(node.leftNode);
        preOrder(node.rightNode);
    }
    // 中序遍历以node为根的二分搜索树, 递归算法
    private void MinInOrder(TreeNode node){
        if(node == null) return;
        MinInOrder(node.leftNode);
        System.out.println(node.data);//访问改节点
        MinInOrder(node.rightNode);
    }

    // 后序遍历以node为根的二分搜索树, 递归算法
    private void PostOrder(TreeNode node){
        if(node == null) return;
        PostOrder(node.leftNode);
        PostOrder(node.rightNode);
        System.out.println(node.data);//访问改节点
    }
}
